This disclosure relates generally to data structures stored in computer memory, and more particularly, to accessing elements in data structures stored in computer memory.
Some currently available processors support single instruction, multiple data (SIMD) operations. A SIMD operation is an operation in which a single instruction operates on two or more data elements items in parallel. For example, a SIMD load instruction may load eight 16-bit values in parallel. In this example, in the same number of clock cycles needed to perform a conventional load instruction that loads a single 16-bit value, a SIMD load instruction would load eight 16-bit values. SIMD processing may be referred to as vector processing. SIMD instructions provide a significant speed up over comparable conventional instructions. However, SIMD instructions may not be suitable for use with known algorithms and data structures. One example processor that supports SIMD instructions is the Pentium® microprocessor via an extension known as multimedia extension (“MMX”) instructions. Another example processor that supports SIMD instructions is the PowerPC™ processor.
The term “process” may generally refer to a computer program that is currently running on a computer system. A process may include one or more threads. The term “thread” may refer to a subset of instructions of a process that perform a specific task. Threads share memory and resources of the process they are part of. Threads may work independently.
An atomic operation is an operation that appears to concurrent processes and threads running on a system to occur instantaneously. An atomic operation is guaranteed to be isolated from concurrently running processes and threads and is said to be “guaranteed” to not be interrupted by other processes and threads. An atomic operation either completes successfully or fails. During an atomic operation to read, modify and write a value at a particular memory address, other processes and threads are held off from reading, writing or operating on the address until the atomic operation successfully completes. An atomic operation may have one or more input arguments used in determining the modified value. Atomic operations may be implemented in software or in hardware.
An array is a data structure in which elements are identified by an index. A program specifies the size of an array it employs and memory for the array is allocated before its use by the program. For efficiency, an array is generally of fixed size and all elements are the same size. During runtime, if a program does not use all of the memory allocated for the array, memory is wasted. On the other hand, if the program needs a larger array at runtime than the predefined size, it's generally inefficient to expand the size of the array.